The Advanced Encryption Standard (AES) is a very well-known encryption algorithm. AES is a block cipher with a block size of 128 bits and a key size of either 128 bits, 192 bits or 256 bits. These three variants are denoted by AES-128, AES-192 and AES-256, respectively. Full details of AES can be found in “Specification for the Advanced Encryption Standard (AES)”, National Institute of Standards and Technology (NIST), Federal Information Processing Standards Publication 197, 2001. Other block ciphers are, of course, also well-known, such as the Data Encryption Standard (DES), Triple-DES (referred to as the Triple Data Encryption Algorithm (TDEA) in the NIST Special Publication 800-67), Blowfish, Camellia, Serpent, etc.
AES is an iterated block cipher. FIG. 1a of the accompanying drawings illustrates the concept of an iterated block cipher. In particular, a round function H is defined. The iterated block cipher involves executing the round function H a number of times, i.e. as a number of iterations, each iteration being referred to as a “round”. In FIG. 1a, there are n rounds. AES-128 has 10 rounds, AES-192 has 12 rounds and AES-256 has 14 rounds. Each round has an associated round key—in FIG. 1a, the round key associated with the i-th round is RKi (i=1, 2, . . . , n). In AES (that is, in AES-128, AES-192 and AES-256), the size of a round key is 128 bits. The inputs to the round function H for the i-th round (i=1, 2, . . . , n) are the round key RKi associated with that round and an amount of data X(i-1) to be operated on: for i=1 (i.e. for the first round), the data to be operated on, X0, is the input plaintext or an initial amount of data (in case of AES, for i=1, the data to be operated on is a function of the input plaintext X0 and an “initial round key” RK0, as detailed later); for i>1 (i.e. for subsequent rounds), the data to be operated on, X(i-1), is the output of the preceding (i−1)-th round. For i=1, 2, . . . , n, the output of the i-th round is Xi=H(Xi-1,RKi), i.e. the result of the round function H operating on the input data Xi-1 based on the round key RKi: the output Xn of the n-th round (i.e. the final round) is the ciphertext; for i<n, the output of the i-th round, Xi, forms the input to the next (i+1)-th round. The round function is normally the same for all rounds. However, it is possible that the round function may be different for some rounds than for other rounds—for example, in AES, the round function for the final round is a modified version of the round function for the other preceding rounds (insofar as it omits a certain processing step, as detailed later). For an iterated block cipher (e.g. AES), the round keys RKi are typically derived from the cipher's (initial) key using a key scheduling algorithm. Again, other iterated block ciphers are, of course, also well-known, such as DES, Triple-DES, Blowfish, Camellia, Serpent, etc.
Some iterated block ciphers (such as AES, Serpent, 3-Way, SAFER, SHARK and Square) involve a so-called “substitution-permutation (SP) network” (or “substitution-linear-transformation network”). In an SP network, the round function H can usually be divided into a round key addition layer, a substitution layer and a permutation or linear transformation layer. An example round function of an SP network is illustrated in FIG. 1b. The input to the round function is a block of data X and a round key RK. The key addition layer combines the input data X with the round key RK (e.g. as a bit-wise addition of X and RK modulo 2, i.e. as an XOR, denoted by ⊕ in FIG. 1b). The substitution layer makes use of one or more substitution boxes (or S-boxes) which each take a respective part of the output of the key additional layer and replace that part with a different value based on a invertible (or one-to-one) mapping defined by that S-box. In FIG. 1b, t S-boxes S1, . . . , St are illustrated they may be the same as each other or they may be different from each other. The permutation layer then takes the outputs of the S-boxes and permutes this total output from the substitution layer (e.g. as a permutation of the bits of the total output). However, it is possible that the round function H of an SP network performs the key addition layer, the substitution layer and the permutation layer in a different order. For example, the AES round function first applies a substitution layer (referred to as the “SubBytes” operation in AES). Next, a permutation layer (comprising the AES “ShiftRows” operation and the AES “MixColumns” operation) is applied to the output of the AES substitution layer. Finally, a key addition layer (referred to as the “AddRoundKey” operation in AES) is applied to the output of the AES permutation layer.
As mentioned before, it is possible that the round function of an SP network may be different for some rounds than for other rounds—for example, the final round of AES does not include the MixColumns operation. In an SP network, it is also possible that an operation is performed on the input plaintext before the first round is performed. For example, AES uses an additional key addition layer before the first AES round is applied. More precisely, an additional AES round key RK0 is defined (RK0 is referred to as the “initial round key” in AES). Like the round keys associated with the AES rounds, RK0 is derived from the AES key using the AES key scheduling algorithm. The input for the first AES round is the XOR of the plaintext X0, and the initial round key RK0. Moreover, in an SP network it is also possible that an operation is performed on the output of the final round. The output of this operation is then the ciphertext. In AES this is not the case; in other words, the output of the final AES round is the ciphertext.
In an SP network as described above, either a round key addition layer is followed by a substitution layer or a substitution layer is followed by a round key addition layer. For example, in AES a round key addition layer is followed by the substitution layer of the next AES round. In the examples described in this document that involve a key addition layer and a substitution layer (or a part of these layers), it is assumed without loss of generality that a round key addition layer is followed by a substitution layer. However, if required, the techniques described in those examples can also be used in case a substitution layer is followed by a key addition layer, by making suitable adjustments to the described examples where necessary in ways which will be familiar to the skilled person. For example, such adjustments are required to apply the techniques to the final AES key addition layer.
A key addition layer and the substitution layer performed directly after the key addition layer may be viewed as comprising a number of parallel operations (which may be identical if a single S-box is used for the substitution layer). This operation is depicted in FIG. 1c of the accompanying drawings (note that, in FIG. 1c, the permutation layer of the round function is not illustrated). The inputs to the operation are a part, x, of the initial input data X to be processed (e.g. an intermediate result of the cipher, such as part of a result from another round) and a corresponding part, k, of the round key RK. In the operation, a bit-wise addition of x and k modulo 2 is performed (i.e. an XOR denoted by ⊕ in FIG. 1c). Next, the result of this addition is input to an S-box, denoted by S in FIG. 1c. The output of the operation is denoted by S(k⊕x), as shown in FIG. 1c. AES uses one fixed S-box mapping an 8 bit input to an 8 bit output. In AES, the size of the data block is 128 bits (i.e. 16 bytes), and x and k are each one byte—hence, the key addition layer and the substitution layer of an AES round may be viewed as comprising 16 identical parallel operations of the type shown in FIG. 1c. The round function for other iterated block ciphers that are SP networks may involve different numbers of operations of the type shown in FIG. 1c and, depending on whether or not they use the same S-box, they may or may not be identical to each other.
A white-box environment is an environment in which an adversary has complete access to the implementation of an algorithm and its execution environment. For example, the adversary may be able to: (1) trace program instructions of the implementation, (2) view the contents of memory and cache, including secret data, (3) stop execution at any point and run an off-line process, and (4) alter code or memory contents at will. To this end, the adversary may be able to make use of existing tools such as debuggers, decompilers, emulators, etc.
White-box cryptography aims at protecting a cryptographic key in a white-box environment, i.e. so that even if an adversary has complete access to the implementation of a cryptographic algorithm (such as source-code, which may be obfuscated, or executable files) and the environment in which that implementation is to be run (e.g. the adversary can execute the implementation in a debug mode to access values of data being stored in memory or to determine the sequence of operations performed), the adversary should not be able to deduce the cryptographic key that is being used (or the round keys that are being used in case of an iterated block cipher). A white-box implementation of AES is described in “White-Box Cryptography and an AES Implementation”, Chow et al., Selected Areas in Cryptography, Lecture Notes in Computer Science, Volume 2595, pp. 250-270, 2003, referred to herein as CHOW.
A cryptanalysis of the white-box AES implementation in CHOW is presented in “Cryptanalysis of a White Box AES implementation”, Billet et al., Selected Areas in Cryptography, Lecture Notes in Computer Science, Volume 3357, pp. 227-240, 2005, referred to herein as BILLET. In “Cryptanalysis of a Generic Class of White-Box Implementations”, Michiels et al, Selected Areas in Cryptography (SAC), Lecture Notes in Computer Science, Volume 5381, pp. 414-428, 2009, referred to herein as MICHIELS, the cryptanalysis of the white-box AES implementation presented in BILLET is generalized for a generic class of SP networks (AES-128, AES-192 and AES-256 belong to this generic class of SP networks).
The white-box implementation in CHOW involves encoding intermediate results of the processing (e.g. the output of a round) using white-box encodings. A white-box encoding is a secret encoding, and the objective of using white-box encodings is to prevent an adversary from deducing the cryptographic key from the white-box implementation (e.g. by deducing the cryptographic key from intermediate results of the processing). The attacks in BILLET and MICHIELS exploit the fact that the intermediate results of the white-box implementation in CHOW are encoded using fixed white-box encodings—in other words, the white-box encoding used to encode an intermediate result is identical for different executions of the white-box implementation of the algorithm. A countermeasure against the attacks in BILLET and MICHIELS is disclosed in WO2010102960. This countermeasure uses so-called “self-equivalences” of the AES S-box. A self-equivalence is defined as a pair of invertible affine mappings (G, g) from R to R (where R is the range of possible inputs and outputs of the S-box under consideration which, is usually Z2n for some integer n and, in the case of AES, is Z28, i.e. n=8 in the case of AES) with the property that g°S°G−1=S; in other words, with the property that S(y)=g(S(G−1(y))) for all y∈R. In the rest of the document, we shall refer to R=Z2n, but it will be appreciated that R may be a more general range of values. In particular, this implies that the output of S equals g(S(y)) if the input equals G(y), as depicted in FIG. 2 of the accompanying drawings. In “A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms”, Biryukov et al., Advances in Cryptology, Eurocrypt 2003, Lecture Notes in Computer Science, Volume 2656, pp. 33-50, 2003, referred to herein as BIRYUKOV, it was shown that the number of self-equivalences for the AES S-box equals 2040.
As described briefly below, self-equivalences of an S-box can be used as a security measure in a white-box implementation more detailed information on this can be found in WO2010102960. In the description below, it is assumed without loss of generality that all white-box encodings are invertible affine mappings. Additional non-linear white-box encodings can be added to the implementation after the techniques described below have been applied, in ways which will be familiar to the skilled person. Further, it is assumed that white-box encodings α and β are used to encode the input and the output of an S-box, respectively. In the white-box implementation, the mappings α and β are composed with the S-box mapping to protect their confidentiality, and the result is denoted by T (also referred to as a T-box), as shown in FIG. 3 of the accompanying drawings. Note that T=β°S°α−1. Typically, T is implemented as a look-up table in the white-box implementation—in the case of AES where the inputs and the outputs of the S-box (and hence the T-box) are one byte, the S-box and hence the T-box consist of 28=256 entries, the size of each entry being one byte. In the white-box implementation, every instance of an S-box may use unique encodings α and β (and consequently, may be implemented using a unique look-up table) for example, whilst AES uses the same S-box for all of the operations (of the type shown in FIG. 1c), each of these operations could make use of their own respective α and β to result in different T-boxes being used. Alternatively, several instances of the S-box may use the same encodings α and β, which may reduce the implementation size of the white-box implementation (through re-use of a look-up table).
The self-equivalences of the T-box are related to the self-equivalences of the corresponding S-box. More precisely, if the sets of self-equivalences of the S-box and the T-box are denoted by EQ(S)={(Gλ,gλ)|gλ°S°Gλ−1=S and (Gλ,gλ) is a pair of invertible affine mappings from Z2n to Z2n} and EQ(T)={(Eφ,eφ)|eφ°T°Eφ−1=T and (Eφ,eφ) is a pair of invertible affine mappings from Z2n to Z2n} respectively, then for every λ, there exists a unique φ such that Eφ=α°Gλ°α−1 and eφ=β°gλ°β−1 and for every φ, there exists a unique λ such that Gλ=α−1°Eφ°α and gλ=β−1°eφ°β. In particular, the size of the set EQ(T) is equal to the size of the set EQ(S) (which, for AES, is 2040).
As described in WO2010102960, the self-equivalences of a T-box can be used to apply a “variable encoding” to the input and the output of a T-box, in that the encoding can vary in different executions of the white-box implementation. To see how this can be done, observe that β(S(y)) is the output of the T-box if α(y) is the input to the T-box. It follows that if Eφ(α(y)) with (Eφ,eφ)∈EQ(T) is input to the T-box, then the output of the T-box equals eφ(β(S(y))) (as shown in FIG. 3). In this way a variable encoding can be applied to the input and the output of a T-box, using only one instance of the T-box in the implementation, with the variable encoding being indexed by φ. For instance, in the white-box implementation the value of φ can be made dependent on several non-encoded intermediate values of the encryption (or decryption) operation, as detailed in WO2010102960.
An intermediate result of the encryption (or decryption) operation that is neither an input to nor an output of an S-box may use a variable encoding that is not associated with a self-equivalence of a T-box. For example, a specific byte of such an intermediate result may be associated with a set {τδ|τδ is an invertible affine mapping from Z28 to Z28} consisting of white-box encodings. The encodings τδ may be secret encodings. This set is selected when the white-box implementation is generated. In every execution of the white-box implementation, one of the encodings in this set is applied to the intermediate result. The value of δ (used to select a particular encoding from the set) can also be made dependent on several non-encoded intermediate values of the encryption (or decryption) operation. Re-encodings can be applied to transform a variable encoding from one set to a variable encoding from a different set (for example, such a re-encoding can be implemented as one or more look-up tables in the white-box implementation). As a result, an intermediate value of the white-box implementation that is neither an input to nor an output of an S-box can also be encoded using variable white-box encodings in that the encoding can vary in different executions of the white-box implementation. In other words, even if a non-encoded intermediate value y (e.g., y being a non-encoded input to the T-box) is the same in different executions of the white-box implementation (for example, when encrypting different plaintexts using the same key), the encoded value of y (for example, Eφ(α(y)) being the encoded input to the T-box) may differ. As detailed in WO2010102960, this property prevents the attacks presented in BILLET and MICHIELS.
In the white-box implementation, the indices of the variable encodings have to be maintained/stored. In particular, an index is required as input to a re-encoding (transforming a variable encoding from one set to a variable encoding from a different set) and at some point in the implementation the variable encodings applied to the intermediate results of the encryption (or decryption) operation have to be removed, i.e. all white-box encodings need to be removed to compute the output ciphertext (or output plaintext in case of decryption).
Many applications in which white-box cryptography is deployed require that it is possible to provide an updated cryptographic key (such as an AES key) to the white-box implementation. One possibility to update the cryptographic key is to update all look-up tables in the white-box implementation that are dependent on the cryptographic key. This is described, for example, in WO2008142612. Alternatively, all look-up tables of a white-box implementation can be updated to update the cryptographic key. However, in certain applications the key update needs to be distributed using a limited amount of bandwidth. A pay-TV conditional access system is an example of such an application. For such applications, schemes are required that implement a smaller key update size than set out above.
Schemes for white-box implementations with a small key update size are described in WO2010146140 and WO2010146139. In these schemes, the cryptographic key (such as an AES key) is first expanded; that is, first the round keys are computed from the initial cryptographic key using the key scheduling algorithm associated with the cryptographic algorithm (the set of round keys associated with a cryptographic key is also referred to as an expanded key in the following). Next, the round keys are encoded using white-box encodings. Finally, the encoded round keys are distributed, after which they can be used as an input to the white-box implementation of the cryptographic algorithm. In the schemes presented in WO2010146140 and WO2010146139, the size of each encoded round key is the same as the size of a non-encoded round key. Hence, the size of the key update information (comprising the set of encoded round keys) is equal to the size of the expanded key (i.e. the total size of the set of non-encoded round keys). AES-128 has 11 round keys (comprising one round key associated with each of the 10 AES rounds and an initial round key) and each round key consists of 16 bytes—this means that in these update schemes 11×16=176 encoded round key bytes need to be distributed to update an AES-128 key. For AES-192, the number of round key bytes equals 13×16=208 and for AES-256, this number equals 15×16=240. This is a significantly smaller amount of data than having to distribute update look-up tables for the white-box implementation.